Let L ω ∞ω be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n -1 satisfies certain simple conditions on its growth rate, then for every σ∈ L ω ∞ω , the probability that σ holds for the (...) random graph on n vertices converges. In fact, if $p(n) = n^{-\alpha}, \alpha > 1$ , then the probability is either smaller than 2 -n d for some $d > 0$ , or it is asymptotic to cn -d for some $c > 0, d \geq 0$ . Results on the difficulty of computing the asymptotic probability are given. (shrink)

For every k ∈ ω, there is an infinite set $A_k \subseteq \omega$ and a d(k) ∈ ω such that for all $Q_0, Q_1 \subseteq A_k$ where |Q 0 | = |Q 1 or $d(k) , the structures $\langle \omega, +, Q_0\rangle$ and $\langle \omega, +, Q_1\rangle$ are indistinguishable by first-order sentences of quantifier depth k whose atomic formulas are of the form u = v, u + v = w, and Q(u), where u, v, and w are variables.